/**
 * 合并K个升序链表
 * 分治思想：将 k 个链表配对并将同一对中的链表合并；第一轮合并以后， kk 个链表被合并成了2/k个链表，平均长度为  k/2n，
 * 然后是4/k个链表， 8/k个链表等等；重复这一过程，直到我们得到了最终的有序链表。
 */
class MergeKListsFenZhi {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int l,int r){
        if(l==r){
            return lists[l];
        }
        if(l>r){
            return null;
        }
        int mid=(l+r)/2;
        return mergeTwoList(merge(lists,l,mid),merge(lists,mid+1,r));
    }
    public ListNode mergeTwoList(ListNode headA,ListNode headB){
        if(headA==null||headB==null){
            return headA!=null?headA:headB;
        }
       ListNode newHead=new ListNode();
       ListNode cur=newHead;
       while(headA!=null&&headB!=null){
           if(headA.val<headB.val){
               cur.next=headA;
               cur=headA;
               headA=headA.next;
           }else{
               cur.next=headB;
               cur=headB;
               headB=headB.next;
           }
       }
       if(headB!=null){
           cur.next=headB;
       }
       if(headA!=null){
           cur.next=headA;
       }
       return newHead.next;
    }
}